\part{Introduction}

\chapter{Overview}


\section{Turing Machine}

从数学和哲学上来对计算进行定义时，计算机可以被看成是一个图灵模型，计算机科学可以被定义为“和计算机相关的问题”。

1937年，Alan Turing首次提出了图灵模型，所有的计算都可以在图灵机上执行，而且图灵模型建立在人们进行计算过程的行为上，这些行为可以抽象到图灵模型中。

在引入图灵模型之前，计算机被定义为一个数据处理器的黑盒，可以接收输入数据、处理数据并产生输出数据，因此只能表示用于完成特定任务的专用计算机（或者处理器）。

图灵模型增加了一个额外的元素（程序），从而可以适用于通用计算机。其中，程序用于指示计算机对数据进行处理的指令集合。

基于通用图灵机建造的计算机都是在存储器中存储数据，并且输出数据依赖输入数据和程序的结合作用。

\begin{compactitem}
\item 对于相同的数据输入，如果改变程序，则可以产生不同的输出；
\item 对于相同的程序，如果改变数据输入，则可以产生不同的输出；
\item 如果输入数据和程序保持不变，则输出结果也将不变。
\end{compactitem}

通用图灵机是对现代计算机的首次描述，因此现代计算机和通用图灵机可以执行任何可计算的运算，用户仅需要提供数据以及处理数据的程序。



\section{Von Neumann}




在1944～1945年期间，von Neumann指出程序指令和数据在逻辑上是相同的，因此程序也可以保存在存储器中。

现代计算机都是以von Neumann模型为基础的，并且可以划分为4个子系统：存储器、算术逻辑单元、控制单元和输入/输出单元。

\begin{compactitem}
\item 存储器用于保存在处理过程中的数据和程序；
\item 算术逻辑单元用于执行算术运行和逻辑运算；
\item 控制单元用于对存储器、算术逻辑单元和输入/输出等子系统进行控制操作；
\item 输入子系统负责从计算机外部读入数据和程序；
\item 输出子系统负责将计算机的处理结果写入到计算机外部。
\end{compactitem}

早期的计算机系统结构中，只有数据才保存在存储器中，但是von Neumann模型要求程序也必须存储在内存中，从而导致了和早期计算机系统结构的完全不同。

在von Neumann模型中，完成某一任务的程序通过操作一系列的开关或改变其配线来实现。

在现代计算机系统结构中，数据和程序具有相同的格式，因此存储单元可以存储程序及其响应数据，实际上它们都是以位模式（0和1序列）存储在内存中的。

另外，von Neumann模型中的程序由一组数量有限的指令组成，并且指令本身是顺序执行的，任何时刻只能有一条指令处于执行状态。

具体来说，控制单元从内存中读取一条指令，译码器解释指令，然后处理器执行指令。实际上，一条指令也可能请求控制单元来跳转到其前面或后面的指令并继续执行，但是指令仍然是顺序执行的，跳转指令本身也是在指令的执行序列中。

von Neumann模型的初始条件就是指令的顺序执行，而且计算机已经进化为以最高效的顺序来执行程序指令。

\section{Hardware}


von Neumann模型将现代计算机清楚地定义为数据处理机，其硬件也都基于von Neumann模型，分别用于接收输入数据，处理并输出相应的结果。

基于von Neumann模型的计算机都包含硬件、软件和数据，虽然von Neumann模型并没有定义数据存储格式，但是二进制计算机中的数据都是以二进制格式存储在计算机内部的，只是在计算机外部可以针对不同的用户表现为不同的形式。

计算机以及数据处理表示法开创了数据组织技术，这样就可以在将数据存储到计算机中之前，有效地将数据组织成不同的实体和格式。

为了对数据组织进行进一步抽象，通过数据结构可以将组合相同或不同类型的数据到特定的类属中。例如，文件系统的本质可以认为是抽象数据类型。

在引入文件系统之后，数据被组织为许多小的单元，并且进一步由这些小的单元组成更大的单元，这样针对不同的目的也就产生了不同的文件系统结构等。

在现代计算机科学中，原子数据汇集成记录、文件和数据库等。

\subsection{CPU}

在大多数系统结构中，所有的数据操作都由CPU完成，CPU（Central Process Unit）由三个组成部分组成。

\begin{compactitem}
\item 算术逻辑单元（ALU）
\item 控制单元
\item 寄存器组
\end{compactitem}

ALU对数据进行逻辑、移位和算术运算。

\begin{compactitem}
\item 逻辑运算包括非、与、或和异或等，它们把输入数据作为二进制模式，运算的结果也是二进制模式。
\item 移位运算包括逻辑移位和算术移位，其中：

\begin{compactitem}
\item 逻辑移位运算用于对二进制位进行向右或向左的移位；
\item 算术移位运算用于对整数执行用2除操作或乘一个整数。
\end{compactitem}

\item 某些专门硬件可以用于提高算术运算的效率。
\end{compactitem}

控制单元控制各个子系统的操作，具体来说控制是通过从控制单元发送到其他子系统的信号来完成的。

寄存器是用于临时存放数据的高速存储设备，常用的寄存器包括：

\begin{compactitem}
\item 数据寄存器

数据寄存器用于存储输入数据、中间结果和最终结果。

\item 指令寄存器

CPU从内存中逐条读取指令时将会把读取出的指令存储在指令寄存器（IR）中，然后再解释和执行指令。

\item 程序计数器

程序寄存器（PC）保存当前正在执行的指令，并且在当前的指令执行完毕后通过对程序计数器自动加1来指向下一条指令的内存地址。
\end{compactitem}


通用计算机使用程序来处理数据，程序和数据都在内存中，CPU使用重复的机器周期来执行程序中的指令，在任何时刻都只有一条指令在运行。

在每一个机器周期中，CPU都按照取指令、译码和执行的步骤执行指令。


在取指令阶段，控制单元将下一条要指令的指令复制到CPU的指令寄存器中，被复制指令的地址保存到程序计数器中，程序计数器在复制完成后自动加1来指向内存中的下一条指令。

在译码阶段，控制单元对指令进行译码并产生一系列系统可以执行的二进制代码。

在执行阶段，控制单元发送指令到CPU的相应部件并执行任务，例如控制单元可能通知系统从内存中加载（读）数据项，或者是通知算术逻辑单元对寄存器中的内存进行运算后将结果进行保存。

\begin{compactitem}
\item 流水线技术允许控制单元同时执行两个或三个阶段来提高吞吐量，这样下一条指令的处理可以在前一条结束前开始。
\item 并行处理通过使用多指令流处理多数据流来改善吞吐量。
\end{compactitem}




\subsection{Memory}

计算机中的输入/输出设备可以分为两大类：非存储设备和存储设备。

\begin{compactitem}
\item 非存储设备（包括键盘、监视器和打印机等）本身不能存储信息，但是可以使得CPU和内存和外界通信。
\item 存储设备通常分为磁介质（例如磁盘）和光介质等。
\end{compactitem}



主存储器是存储单元的集合，每一个存储单元都有唯一的标识（也就是地址），这样就可以在存储器中通过对应的地址来存取每一个字。

RAM（随机存取存储器）是主存储器的组成部分，这里的随机是指可以使用存储单元地址来随机存取一个数据项，不需要存取位于其前面的所有数据项，从而区别于磁带等存储设备。

\begin{compactitem}
\item SRAM（静态RAM）使用触发器门电路来保存数据，而且门可以保持状态（0或1），通电时可以在不需要刷新的情况即可保持数据始终存在。
\item DRAM（动态RAM）使用电容器充电来保持状态1，电容器放电则代表状态0，而且内存单元需要周期性地刷新来维持电容器的状态。
\end{compactitem}

在硬件层次上，每个字都是通过地址来标识的，所有在存储器中唯一可标识的独立地址单元的总数称为地址空间。例如，一个8GB、字长为8字节的内存的地址空间的范围为0到1~048~576。

\begin{table}[htbp]
\centering
\caption{存储单位}
\begin{tabular}{lll}
\hline
单位 & 字节数的准确值 & 字节数的近似值\\
\hline
千字节（KB） & $2^{10}$（1~024）字节 & $10^3$字节\\
兆字节（MB） & $2^{20}$（1~048~576字节）字节 & $10^6$字节\\
千兆字节（GB） & $2^{30}$（1~073~741~824）字节 & $10^9$字节\\
兆兆字节（TB）& $2^{40}$字节 & $10^{12}$字节\\
\hline
\end{tabular}
\end{table}



在计算机内部都是以位模式存储数字并进行计算的，存储地址也是使用位模式（即无符号二进制整数）来表示的。

一般来说，起始地址通常是0，而且如果一个计算机有N个字的存储空间，那么就需要有$\log_2N$位的无符号整数来确定每一个存储单元。




\subsection{Cache}



高速缓冲存储器的存取速度比主存快，但是比CPU及其内部的寄存器慢，通常位于CPU和主存之间。

高速缓冲存储器在任何时刻都含有主存中一部分内容的副本，因此当CPU要存取主存中的一个字时，将按照以下步骤进行：

\begin{compactenum}
\item CPU首先检查高速缓存。
\item 如果要存取的字存在，CPU将其复制，否则CPU将从主存中拷贝一份从需要读取的字开始的数据块，该数据块将覆盖高速缓存中的内容。
\item CPU存取高速缓存被拷贝该字。
\end{compactenum}



实际上，很有可能CPU在下次存取中需要存取上次存取的第一个字的后续字，因此高速缓存可以提高运算的速度。

\begin{compactitem}
\item 如果字在高速缓存中，就立即存取它；
\item 如果字不在高速缓存中，字或整个数据块就会被拷贝到高速缓存中。
\end{compactitem}

根据80/20法则，通常计算机需要花费80\%的时间来读取20\%的数据，也就是说相同的数据往往被存取多次，这样高速缓存可以通过存储20\%的数据来提高80\%的存取速度。





\subsection{BUS}


在现代计算机系统结构中，CPU和内存之间通常由总线（bus）连接在一起。

总线可以被分为三组线路，分别是数据总线、地址总线和控制总线。



数据总线（Data Bus）的每一根线上每次传送1个位的数据，而且线的数量取决于字的大小。

\begin{compactitem}
\item 32位计算机使用32根数据总线来每次传送4个字节，这样同一时刻就可以同时传送32位的字。
\item 64位计算机使用64根数据总线来每次传送8个字节，这样同一时刻就可以同时传送64位的字。
\end{compactitem}

地址总线（Address Bus）允许访问存储器中的某个字，线的数量取决于存储空间的大小。例如，如果存储器容量为$2^n$个字，那么地址总线一次需要传送n位的地址数据，也就是说地址总线中的线的数量就是n。

控制总线（Control Bus）负责在中央处理器和内存之间传送信息。例如，必须有一个代码从CPU发往内存来指定进行的是读操作还是写操作。

控制总线的数量取决于计算机所需要的控制命令的总数。例如，如果计算机有$2^m$条控制命令，那么m条控制总线就就可以定义$2^m$个不同的操作，那么m根控制总线就可以满足需求。


输入/输出设备与CPU以及内存的本质不同，因此不能直接与连接CPU和内存的总线相连。

\begin{compactitem}
\item 输入/输出设备是机电、光磁设备。
\item CPU和内存都是电子设备。
\end{compactitem}

输入/输出设备的速度要显著低于CPU和内存，因此必须通过中介来与CPU和内存通信。

一般来说，输入/输出设备通过输入/输出控制器或连接器来与总线沟通，然后再由总线与CPU和内存等进行沟通。

输入/输出控制器（或者说接口）可以是串行或并行的设备，用来消除输入/输出设备与CPU及内存在本质上的障碍。

\begin{compactitem}
\item 串行控制器只有一根数据线进行连接。
\item 并行控制器需要多根数据线进行连接，一次能同时传送多个位。
\end{compactitem}

SCSI（小型计算机系统接口）是一个8、16或32线的并行接口，并且提供了菊花链连接。

\begin{compactitem}
\item 连接链的两端都必须有终结器。
\item 每个设备都必须有唯一的地址（目标ID）。
\end{compactitem}

1394是一种高速的串行接口，数据采用数据包的形式传送。

\begin{compactitem}
\item 可以在一条菊花链或树型连接（只用一根线）上连接多达63个设备。
\item 不需要SCSI中的终结器。
\end{compactitem}

USB（通用串行总线）控制器是一种串行控制器，根集线器可以连接多个设备到一个USB控制器上。例如，USB2.0支持多达127个设备组成树状拓扑结构连接到一个USB控制器上，其中控制器作为树的根，集线器作为中间节点，设备作为末端节点。

USB控制器（根集线器）与其他集线器的不同在于控制器能感知树中其他集线器的存在，而其他集线器则是被动的设备，它们只是简单地传送数据。

USB支持热交换设备，因此无需关闭计算机就可以直接移除和连接，当集线器被从系统中移除时，与该集线器相连地所有设备和其他集线器也被移除。

USB使用4根线的电缆，其中两根线（+5伏和地）用来为低压设备（例如键盘和鼠标）提供电压，高压设备则需要连接到电源上。

集线器从总线取得电压，从而为低压设备提供电压，其他的两根线进行缠绕来减少噪声和传送数据、地址和控制信号。

USB2.0提供三种传输速率：1.5Mbps、12Mbps和480Mbps。

\begin{compactitem}
\item 低速率可以用于低速设备（例如键盘和鼠标）。
\item 中速率用于打印机。
\item 高速率用于大容量的存储设备。
\end{compactitem}

USB控制器以包的形式传输数据，每个包含有地址部分（设备标识）、控制部分和数据部分，所有设备将接收到相同的包，但是只有具有数据包中所定义的地址的设备能够识别和接受包。

通常情况下，CPU使用相同的总线在主存和输入/输出设备之间读写数据，唯一的不同是指令。

\begin{compactitem}
\item 如果指令涉及主存中的字，那么数据会在主存和CPU之间传送。
\item 如果指令涉及输入/输出设备，那么数据会在输入/输出设备和CPU之间传送。
\end{compactitem}


输入/输出设备的寻址方式有两种，分别是I/O独立寻址和I/O存储器映射寻址。

\begin{compactitem}
\item 在I/O独立寻址中，用来从内存读/写的指令完全不同于用来从输入/输出设备的读/写指令。
\item 在I/O存储器映射寻址中，CPU把I/O控制器中的每个寄存器看作是内存中的字。
\end{compactitem}

为了把数据从I/O设备传输到CPU和内存，并使CPU的操作在某种程度上和输入/输出设备保持同步，现在已经发展出三种不同的方法。

\begin{compactitem}
\item 程序控制输入/输出
\item 中断控制输入/输出
\item 直接存储器存取（Direct Memory Access）
\end{compactitem}

在程序控制输入/输出中采用最简单的一种同步，CPU等待I/O设备，而且CPU和I/O设备之间的数据传输通过程序中的指令实现。

具体来说，当CPU遇到一条I/O指令时就停止工作并等待，直到数据传输完毕，CPU不断地查询I/O设备地状态来确定数据传输完成。

程序控制输入/输出的问题在于在每一个单元数据被传输时，CPU都要查询I/O设备的状态，而且数据的输入/输出都要经过内存。

在中断控制输入/输出中，CPU指示I/O设备开始传输数据，并且在I/O设备准备就绪后通知（中断）CPU，不过数据的输入/输出仍然要经由内存。

直接存储器存取（DMA）用于在高速I/O设备间传输大量的数据块（例如磁盘、内存），这样就可以不需要经由CPU的数据传输，不过需要单独的DMA控制器来承担CPU的运算。

DMA控制器中有寄存器，可以在内存传输前后保存数据块。

当准备好传输数据时，由DMA控制器通知CPU来获得总线的使用权，CPU继而停止使用总线并转交给DMA控制器使用。

在内存和DMA之间的数据传输完成后，CPU继续使用总线，实际上CPU只是在一小段时间内是空闲的，即在DMA和内存间传输数据时才会空闲。




\section{Software}

在早期的计算机中，用户都是在计算机外部进行编程的，程序体现为对系列开关的开闭和配线的改变。

von Neumann模型要求内存必须可以存储程序，而且程序必须是有序的指令集，其中的每一条指令操作一个或者多个数据项。例如，在最简单的相加操作中也包含四个独立的指令集，首先输入两个数据，然后将二者相加并将结果保存在存储器中，最后输出结果。

通过仔细地定义计算机可以使用的不同指令集，可以使指令集具备重用性，这样就可以组合不同的指令来创建任意的程序，每个程序本身可以是不同指令的不同组合。


计算机语言是指令的抽象，早期的计算机语言称为机器语言（位模式），后来进化为使用符合来表示二进制模式。



不同的开发范式产生了不同种类的计算机语言，例如：

\begin{compactitem}
\item 过程式语言
\item 面向对象语言
\item 函数式语言
\end{compactitem}





\section{Algorithm}


为了解决问题，首先可以以顺序方式来开发程序，然后可以改进程序算法，从而尽量找到合适的指令序列来解决问题。

用户在完成某一任务时，往往需要遵循程序设计原理和规则，这些原理和规则的综合就是现代软件工程。

操作系统是公用指令的抽象，最初的操作系统仅仅是为程序访问计算机部件提供方便。例如，读入和写入数据的操作就可以被提取出来组成公共的组件。


\chapter{Numberic}

\section{Overview}

为了把数据存储到计算机中，作为“纸和笔的代表物”，数字系统可以将不同的数字转换为统一的格式。

具体来说，数字系统定义了如何使用特定的符号来表示数字，不同的记数系统有不同的表示方法，其基础都是位置记数法。

在使用位置记数法的数字系统中，数字中的符号所处的位置决定了其表示的值，每个位置有一个位置量与其相关联。


\begin{quote}
\textsl{使用非位置记数法的记数系统（例如罗马数字）并不用在计算机中，它们仍然使用有限的数字符号，每个符号有一个值，但是符号所处的位置通常与其值无关——每个符号的值是固定的。}
\end{quote}

\begin{table}[htbp]
\centering
\caption{罗马数字系统的符号取值}
\begin{tabular}{l|ccccccc}
\hline
符号 & I &V &X &L & C& D &M\\
\hline
值 & 1 & 5 & 10 & 50 & 100 & 500 & 1000\\
\hline
\end{tabular}
\end{table}

\begin{quote}
\texttt{玛雅文明发明了位置化的二十进制数字系统，该系统使用的20个符号建立在3个更简单的符号之上，其先进特征在于它有符号0。}

\texttt{巴比伦文明发展了首个位置化数字系统，在继承了闪族人和阿卡得人的数字系统的基础上，发展出位置化的六十进制数字系统，而且60现在仍然用于时间和角度记数中。}
\end{quote}



在不同的数制之间转换时，数字的值是等价的。



用户可以将十进制数转换为与其等值的任意底（base），其需要两个过程，分别用于整数部分和小数部分。

\begin{compactitem}
\item 整数部分需要连除；
\item 小数部分需要连乘。
\end{compactitem}



现在，Internet的公共底是256，因此可以使用256个符号来表示该数字系统中的数字，设计者使用十进制数字0到255来表示其中一个符号。
\[S=\{0,1,2,3,\cdots,255\}\]

IP地址系统中的数字总是以$S_1.S_2.S_3.S_4$的形式出现，不过IP地址也可以表示为位模式，其中使用32位表示一个地址，在点十进制记数法的一个符号占用8个数字。

\section{Data Type}

在现代计算机中，数据可以以不同的形式出现（例如数字、文字、音频、图像和视频等），但是所有计算机外部的数据都采用统一的数据表示法转换后才能存储到计算机中。

为了把不同的数据类型存储到计算机中，需要使用统一的方式来将数据存储到计算机内部，并且在从计算机输出时再还原成对应的数据类型。

通常来说，所有的数据都是以位模式存储在计算机内部的，而且现在提供了多种方法来处理数字的正负问题。例如，整数可以使用下面的不同的格式进行存储：

\begin{compactitem}
\item 无符号格式

通常计算机都定义了一个最大无符号整数的常量，称为最大无符号整数（$2^n-1$）。

\item 符号加绝对值


\item 二进制补码
\end{compactitem}

为了更有效地利用内存，无符号和有符号的整数的存储方式是不同的，因此在对数字类型的数据进行进一步扩充时，实数使用浮点格式进行存储。

计算机使用两种不同的方法（定点和浮点）来表示小数点。

\begin{compactitem}
\item 定点用于把数字作为整数存储（没有小数部分）；
\item 浮点用于把数字作为实数存储（带有小数部分）。
\end{compactitem}



不同的计算机系统引入了相应的编码系统（例如ASCII和Unicode等）来保存文本数据。

\begin{compactitem}
\item 通过采样、量化和编码来存储音频数据；
\item 通过光栅和矢量模式来存储图像数据；
\item 通过图像随时间的变化来存储视频数据。
\end{compactitem}


\subsection{bit}


位（bit，binary digit）是数据存储在计算机中的最小单位i，本身只能是0或1。

具体来说，位代表设备的两种状态中的一个，一般使用1表示高电位，0表示低电位，因此现代计算机就是使用多种不同的双态设备来存储数据的。

\subsection{byte}


计算机根据位模式来存储数据，位模式（或位流）可以进一步进行扩展。例如，长度为8的位模式称为1个字节（byte），计算机一次能处理的最长位数称为字（word）。

实际上，数据是以字的位组的形式在内存中传入和传出的。

为了在存储数据时消耗较少的存储空间，可以对数据进行压缩后再存储。



在数据传输和存储时都要进行错误校验和纠正。




\section{Integer}


整数是完整的数字（没有小数部分），并且可以被当作小数点位置固定的数字，小数点固定在最右边。



计算机存储正负数的方式是不同的，定点表示法用于存储整数，其中最高位为1表示负数，最高位为0表示正数。

\subsection{Unsigned Integer}


无符号整数是永远不会为负的整数。


\subsection{Signed Integer}

在存储有符号整数时，可以使用符号加绝对值格式，其中最高位用于指示符号且其余位定义绝对值，符号和绝对值互相分开。


\section{Complement}


几乎所有的计算机都使用二进制补码表示法来存储位于n位存储单元中的有符号整数。

无符号整数的有效范围被分为两个相等的子范围，其中第一个子范围用来表示非负整数，第二个子范围用于表示负整数。

在二进制补码表示法中，最左位决定整数的符号，但是符号和绝对值互相分开。

为了获得二进制补码，可以首先转换成二进制反码，然后把结果加1。

在十进制数中，与二进制反码对等的称为十进制反码（例如$1=2-1$和$9=10-1$），因此对于n位的单元可以使用十进制反码表示数字的范围是：\[-[(10^n/2)-1]\sim +[(10^n/2)-1]\]

带有n个数码的十进制反码数字通过下面的方法获得：

\begin{compactitem}
\item 如果数字为正，十进制反码就是其本身；
\item 如果数字为负，将每个数码减9。
\end{compactitem}

在十进制数中与二进制补码对等的称为十进制补码，因此对于n位的单元，使用十进制补码表示数字的范围是：\[-(10^n/2)\sim +(10^n/2-1)\]

带有n个数码的十进制补码数字通过下面的方法获得，先求出该数字的十进制反码，接着给结果加1。




















































































































